package com.shm.leetcode;

/**
 * 303. 区域和检索 - 数组不可变
 * 给定一个整数数组  nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。
 *
 * 实现 NumArray 类：
 *
 * NumArray(int[] nums) 使用数组 nums 初始化对象
 * int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）
 *
 *
 * 示例：
 *
 * 输入：
 * ["NumArray", "sumRange", "sumRange", "sumRange"]
 * [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
 * 输出：
 * [null, 1, -1, -3]
 *
 * 解释：
 * NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
 * numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
 * numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
 * numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
 *
 *
 * 提示：
 *
 * 0 <= nums.length <= 104
 * -105 <= nums[i] <= 105
 * 0 <= i <= j < nums.length
 * 最多调用 104 次 sumRange 方法
 */
class NumArray {
    int[] nums;
    int[] sums;
    public NumArray(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        if(n>0){
        sums = new int[n];
        sums[0] = nums[0];
        for(int i=1;i<n;i++){
            sums[i] = sums[i-1]+nums[i];
        }
        }
    }
    
    public int sumRange(int i, int j) {
        // int ans = 0;
        // for(int k=i;k<=j;k++){
        //     ans+=nums[k];
        // }
        // return ans;

        if(i==j){
            return nums[i];
        }
        if(i==0){
            return sums[j];
        }
        return sums[j]-sums[i-1];
    }


    /**
     * 前缀和简介
     * 考虑以下问题：
     *
     * 给定长度 nn 的序列 a：a_{0}, a_{1}, ..., a_{n-1}a
     * 0
     * ​
     *  ,a
     * 1
     * ​
     *  ,...,a
     * n−1
     * ​
     *  ，给每个前缀求一次和，S_{0} = 0, S_{i}=\sum^{i-1}_{j=0}a_{j}S
     * 0
     * ​
     *  =0,S
     * i
     * ​
     *  =∑
     * j=0
     * i−1
     * ​
     *  a
     * j
     * ​
     *   。这些前缀和维护在一个长度 n + 1n+1 数组 S 里, 称为前缀和数组。
     *
     * 有两类在数组 a 上的求和需求
     *
     * 前缀和：求 a[0..i] 的和
     * 区间和：求区间 a[L, R] 的和
     * 对于前缀和，S[i + 1] 刚好就是答案，因为这就是前缀和的定义：S_{i + 1}=\sum^{i}_{j=0}a_{j}S
     * i+1
     * ​
     *  =∑
     * j=0
     * i
     * ​
     *  a
     * j
     * ​
     *  。
     * 对于区间和，解决此问题最直观的方法是枚举 [L, R] 上的所有元素求和：sum(L, R) = \sum_{idx = L}^{R}nums[idx]sum(L,R)=∑
     * idx=L
     * R
     * ​
     *  nums[idx] 。这种方法虽然直观，但是不足是查询一次需要 O(N)O(N) 的时间，并且每来一个新的查询，就要重新枚举元素求和。通过简单的画图推导可以得到答案为 S[R + 1] - S[L]S[R+1]−S[L]
     *
     * 如果查询次数很多，当新查询来时，此前的查询计算的中间结果很多是可以直接用的，新的查询不必重新枚举，例如 此前查询过 sum(5, 10)，现在来了新查询 sum(4, 8) 在计算新查询时，5 ~ 8 这一段在计算此前的查询 sum(5, 10) 的时候已经计算过了，新查询的计算过程可以写成 nums[4] + sum(5, 8)nums[4]+sum(5,8) ，而不用全部枚举。
     *
     * 如果已经有了 前缀和数组，那么通过简单的画图推导可以知道，两个前缀和 S[R + 1] 和 S[L] 的差刚好就是　[L, R] 上的区间和。已有前缀和数组之后，这一步操作就是 O(1)O(1) 的。
     *
     * 现将前缀和数组预处理出来，然后在每次查询中直接通过前缀和数组来计算而不是通过原数组，这是一种缓存中间结果的思想，如果把这一思想执行彻底，可以将所有可能的问题 sum(i, j) 其中 0<=i<=j<=n-1，将计算它们所需的所有中间结果先算一次缓存下来。这里提到的是缓存所有所需的中间结果，而不是子问题的中间结果，因为计算 sum(i, j) 需要的中间结果是前 i-1i−1 个数的和 sum(0,i) 和前 jj 个数的和 sum(0,j+1)。最终 sum(i,j) = sum(0,j+1) - sum(0,i) 这对于所有的区间查询都是适用的。
     *
     * 以上将中间结果缓存思路与动态规划中缓存子问题的解的思路是一致的。
     *
     * 定义 sums[k] 为 [0..k-1] 的和，其中 sums[0] 表示数组中没有数字被选中，sums[1] 表示之选中第一个数 nums[0]。 预先计算 0 ~ k (0<=k<=n-1)(0<=k<=n−1) 的和，这一系列的和都是从 0 开始的，因此称为前缀和。公式如下：
     *
     * k = 0:sum(0,0)=0k=0:sum(0,0)=0
     * 1 <= k <= n-i:sum(0,k) = \sum_{i=0}^{k-1}nums[i]1<=k<=n−i:sum(0,k)=∑
     * i=0
     * k−1
     * ​
     *  nums[i]
     * 此后的区间查询都可以利用公式 sum(i, j) = sums(0, j + 1) - sum(0, i)
     *
     * 在上一章中，我们把线性动态规划中几种主流问题及其对应的 dp 状态设计做了总结。其中最基础的一种是单串 dp[i]，并且只与子问题 i - 1i−1 有关，即 dp[i] = f(dp[i-1])。前缀和就是这种情况，sums[i] 只与 sums[i-1] 有关。推导前缀和数组的过程是 O(N)O(N) 的，如果区间和的查询次数达到了 O(N)O(N) 那么计算区间和的时间复杂度是摊销 O(1)O(1) 的。
     *
     * 以上就是前缀和的基础介绍了，其中比较关键的有两点
     *
     * 预处理前缀和的过程是最简单且最经典的单串动态规划问题。
     * 先将所有位置的前缀和预处理出来，然后再处理区间和的查询，这是一种先缓存中间结果再处理查询的思路，因为这些中间结果在查询时需要反复用到，缓存之后就不用反复计算了，因此花时间预处理这些信息是有效的。
     * 前缀和除了求区间和之外，还有一些其它的应用：
     *
     * 在用 dp 的方式推 sums[i] 的时候，有时求完 sums[i] 需要查询以前算过的结果计算某种指标，需要用其它数据结构将前面的计算结果维护起来，例如哈希表等等，在求每个位置的前缀和的过程中，查询数据结构并更新答案，这是前缀和的一大类问题，变化比较多，力扣上这类题也有很多，在本章最后一节中汇总了一些题目，在下一节也选择了典型题目做讲解。
     * 前缀和的逆运算是差分，对原序列求出其差分序列，然后在对得到的差分序列求其前缀和序列，可以得到原序列，这在处理一些区间修改的问题时很有用，参考后面小节的题目讲解。
     * 前缀和还可以推广到二维上，并用于快速求矩形和，二维前缀和的计算过程是最经典的矩阵上的线性动态规划，参考后面一节的题目和讲解。
     *
     * 复杂度分析
     *
     * 时间复杂度：初始化 O(n)O(n)，每次检索 O(1)O(1)，其中 nn 是数组 \textit{nums}nums 的长度。
     * 初始化需要遍历数组 \textit{nums}nums 计算前缀和，时间复杂度是 O(n)O(n)。
     * 每次检索只需要得到两个下标处的前缀和，然后计算差值，时间复杂度是 O(1)O(1)。
     *
     * 空间复杂度：O(n)O(n)，其中 nn 是数组 \textit{nums}nums 的长度。需要创建一个长度为 n+1n+1 的前缀和数组。
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/dynamic-programming-1-plus/5mt8sh/
     */
    class NumArray_2 {
        int[] sums;

        public NumArray_2(int[] nums) {
            int n =nums.length;
            sums = new int[n+1];
            for(int i=1;i<=n;i++){
                sums[i] = sums[i-1]+nums[i-1];
            }
        }

        public int sumRange(int left, int right) {
            return sums[right+1]-sums[left];
        }
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */